//70 上台阶
/*
给定 n 节台阶，每次可以走一步或走两步，求一共有多少种方式可以走完这些台阶

输入是一个数字，表示台阶数量；输出是爬台阶的总方式

Input: 3
Output: 3

分析：
	定义一个数组 dp， dp[i] 表示走到第 i 阶的方法数。因为
	我们每次可以走一步或者两步，所以第 i 阶可以从第 i-1 或 i-2 阶到达

dp[i] = dp[i-1] + dp[i-2]
*/
//方法一：递归
int climbStairs(int n)
{
	if (n <= 2)
		return n;
	vector<int> dp(n + 1, 1); //n+1个元素
	for (int i = 2; i <= n; ++i)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}
//方法二：空间复杂度O(1)
int climbStairs(int n)
{
	if (n <= 2)
		return n;
	int pre2 = 1, pre1 = 2, cur;
	for (int i = 2; i < n; ++i)
	{
		cur = pre1 + pre2;
		pre2 = pre1;
		pre1 = cur;
	}
	return cur;
}